package com.ling.algorithm;

import java.util.Arrays;

/**
 * author:Neil
 * Time: 17:01
 * Date: 2022/9/5
 * Description:
 * 快速排序法：一种比较高效的排序算法，采用“分而治之”的思想，通过多次比较和交换来实现排序，在一趟排序种把将要排序的数据分成两个独立的部分，对这两个部分进行排序使得其中一部分
 *所有数据比另一部分都要小，然后继续递归排序这两部分，最终实现所有数据有序
 *
 */
public class FastSort {

    public static void fastSort(int[] arr,int left,int right){
        //先过滤不合理请求排序
        if (left>right){
            return;
        }
        //确定基准数
        int base = arr[left];

        int i = left;
        int j = right;
        while (i!=j){

            //寻找比基准数小的数
            while(i<j && base<=arr[j]){
                j--;
            }

            //寻找比基准数大的数
            while(i<j && base>=arr[i]){
                i++;
            }

            //交换位置
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }

        arr[left] =arr[i];
        arr[i] = base;
        //基准数在这里递归就为了左边的数比它小，右边的数比它大
        //排序基准数的左边
        fastSort(arr,left,i-1);
        //排右边
        fastSort(arr,j+1,right);
    }

    public static void main(String[] args) {
        int[] arr= {8, 2,50,-3, 30, 20};
        System.out.println("插入排序前：");
        System.out.println(Arrays.toString(arr));
        fastSort(arr,0,arr.length - 1);
        System.out.println("插入排序后：");
        System.out.println(Arrays.toString(arr));
    }
}
